#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n, m, s;
const int N = 5e5 + 5;
typedef pair<int, int> ppi;

vector<ppi> e[N];
int vis[N], d[N];//vis表示是否出圈，是否以及计算过了，d表示u到s源点的最小距离
int pre[10];//记录前驱点，以便输出最短路的记录

void dijkstra(int s)
{
	//初始化所有的边到s的距离都是无穷大，s到s自己的是0
	for (int i = 0; i <= n; i++)//注意这里的细节，0也要初始化
		d[i] = inf;
	d[s] = 0;//源点到自己的距离是0
	
	//依次枚举的次数
	for (int i = 1; i <= n; i++)
	{
		int u = 0;
		for (int j = 1; j <= n; j++)//依次枚举点到源点的距离最小的那个点
		{
			if(!vis[j] && d[j] < d[u])
				u = j;
		}
		vis[u] = 1;//标记出圈
		
		//依次枚举邻边
		for (auto ed : e[u])
		{
			int v = ed.first, w = ed.second;
			if (d[v] > d[u] + w)
				d[v] = d[u] + w;
		}	
	}
}


priority_queue<ppi> q;

void dijkstra_p(int s)
{
	//初始化边权，所有点到s的距离
	for (int i = 0; i <= n; i++)
		d[i] = inf;
	d[s] = 0;
	q.push({0, s});//先把源点放入队列
	while (q.size())
	{
		auto t = q.top();
		q.pop();
		int u = t.second;
		if (vis[u]) continue;
		vis[u] = 1;
		
		for (auto ed : e[u])
		{
			int v = ed.first, w = ed.second;
			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push({-d[v], v});//技巧，存负数，从而得到小根堆
				pre[v] = u;
			}
		}
	}
}

void dfs_path(int u)
{
	if (u == s)
	{
		cout << u << "->";
		return;
	}
	dfs_path(pre[u]);
	cout << u << "->";
}
int main()
{
	//n:节点个数， m边数， s:起点
	cin >> n >> m >> s;
	int a, b, c;
	//构建有向图
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		e[a].push_back({b,c});
	}
	//常规解法
	//dijkstra(s);
	
	dijkstra_p(s);

	//堆优化版本
	for (int i = 1; i <= n; i++)
	{
		cout << d[i] << " ";
	}
	cout << endl;
	for (int i = 1; i <= n; i++)
	{
		dfs_path(i);
		cout << endl;
	}
		
	return 0;
}
/*
5 7 1
1 3 5
1 4 2
1 5 2
4 2 6
4 3 2
5 3 1
3 2 2
*/